/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 5/28/2008
 */

#ifndef BTNODE_H
#define BTNODE_H

#include "RecordFile.h"
#include "PageFile.h"

//83 is the largest that n can be without overflowing a 1Kb buffer
#define BT_N 83
#define BT_MAX_NUM_POINTERS BT_N
#define BT_MAX_NUM_KEYS BT_N - 1
#define BT_NUM_OVERFLOW_SLOTS 1

#define BT_RECORDID_SIZE sizeof(RecordId)
#define BT_PAGEID_SIZE sizeof(int)
#define BT_KEY_SIZE 4

#define BT_KEY_START 12
#define BT_PTR_START BT_KEY_START + (BT_NUM_OVERFLOW_SLOTS + BT_MAX_NUM_KEYS)*BT_KEY_SIZE
#define BT_NEXT_NODE_PTR BT_PTR_START + (BT_MAX_NUM_POINTERS - 1 + BT_NUM_OVERFLOW_SLOTS)*BT_RECORDID_SIZE

#define RC_NONEMPTY_SIBLING -1015
#define RC_INVALID_LAST_POINTER -1016

static inline int 
_BTGetNumKeys(char buf[]) {
	int nKeys;
	memcpy(&nKeys, buf+4, sizeof(int));
	return nKeys;
}

static inline int 
_BTGetNumPointers(char buf[]) {
	int nPointers;
	memcpy(&nPointers, buf+8, sizeof(int));
	return nPointers;
}

static inline int* getKey(char buf[], int keyNum) {
	return (int*) (buf + BT_KEY_START + BT_KEY_SIZE*keyNum); 
}

static inline RecordId* getRecordId(char buf[], int pointerNum) {
	return (RecordId*) (buf + BT_PTR_START + BT_RECORDID_SIZE*pointerNum); 
}

static inline PageId* getPageId(char buf[], int pointerNum) {
	return (PageId*) (buf + BT_PTR_START + BT_PAGEID_SIZE*pointerNum); 
}

static inline void updateNumKey(char buf[], int numKey) {
	memcpy(buf+4, &numKey, sizeof(int));
	return;
}

static inline void updateNumPointer(char buf[], int numPointer) {
	memcpy(buf+8, &numPointer, sizeof(int));
	return;
}


/**
 * BTLeafNode: The class representing a B+tree leaf node.
 */
class BTLeafNode {
  public:

	BTLeafNode();
   /**
    * Insert the (key, rid) pair to the node.
    * Remember that all keys inside a B+tree node should be kept sorted.
    * @param key[IN] the key to insert
    * @param rid[IN] the RecordId to insert
    * @return 0 if successful. Return an error code if the node is full.
    */
    RC insert(int key, const RecordId& rid, bool overflow = false);

   /**
    * Insert the (key, rid) pair to the node
    * and split the node half and half with sibling.
    * The first key of the sibling node is returned in siblingKey.
    * Remember that all keys inside a B+tree node should be kept sorted.
    * @param key[IN] the key to insert.
    * @param rid[IN] the RecordId to insert.
    * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
    * @param siblingKey[OUT] the first key in the sibling node after split.
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC insertAndSplit(int key, const RecordId& rid, BTLeafNode& sibling, int& siblingKey);

   /**
    * Find the index entry whose key value is larger than or equal to searchKey
    * and output the eid (entry id) whose key value &gt;= searchKey.
    * Remember that keys inside a B+tree node are sorted.
    * @param searchKey[IN] the key to search for.
    * @param eid[OUT] the entry number that contains a key larger              
    *                 than or equalty to searchKey.
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC locate(int searchKey, int& eid);

   /**
    * Read the (key, rid) pair from the eid entry.
    * @param eid[IN] the entry number to read the (key, rid) pair from
    * @param key[OUT] the key from the slot
    * @param rid[OUT] the RecordId from the slot
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC readEntry(int eid, int& key, RecordId& rid);

   /**
    * Return the pid of the next slibling node.
    * @return the PageId of the next sibling node 
    */
    PageId getNextNodePtr();


   /**
    * Set the next slibling node PageId.
    * @param pid[IN] the PageId of the next sibling node 
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC setNextNodePtr(PageId pid);

	bool nextNodePtrIsSet();

   /**
    * Return the number of keys stored in the node.
    * @return the number of keys in the node
    */
    int getKeyCount();
	
   /**
    * Return the number of pointers stored in the node.
    * @return the number of pointers in the node
    */
    int getPointerCount();
 
   /**
    * Read the content of the node from the page pid in the PageFile pf.
    * @param pid[IN] the PageId to read
    * @param pf[IN] PageFile to read from
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC read(PageId pid, const PageFile& pf);
    
   /**
    * Write the content of the node to the page pid in the PageFile pf.
    * @param pid[IN] the PageId to write to
    * @param pf[IN] PageFile to write to
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC write(PageId pid, PageFile& pf);

	void test();

  private:
   /**
    * The main memory buffer for loading the content of the disk page 
    * that contains the node.
    */
    char buffer[PageFile::PAGE_SIZE];

	void _setNextNodePtrFlag() { buffer[0] |= 0x01; }
}; 


/**
 * BTNonLeafNode: The class representing a B+tree nonleaf node.
 */
class BTNonLeafNode {
  public:

	BTNonLeafNode();
   /**
    * Insert a (key, pid) pair to the node.
    * Remember that all keys inside a B+tree node should be kept sorted.
    * @param key[IN] the key to insert
    * @param pid[IN] the PageId to insert
	* @param overflow[IN] if wanting to overflow amount of nodes and pointers
    * @return 0 if successful. Return an error code if the node is full.
    */
    RC insert(int key, PageId pid, bool overflow = false);

   /**
    * Insert a pid to the node to be the last pointer.
    * @param pid[IN] the PageId to insert
    * @return 0 if successful. Return an error code if the node is full.
    */	
	RC insertLastPointer(PageId pid);
	
   /**
    * Insert the (key, pid) pair to the node
    * and split the node half and half with sibling.
    * The sibling node MUST be empty when this function is called.
    * The middle key after the split is returned in midKey.
    * Remember that all keys inside a B+tree node should be kept sorted.
    * @param key[IN] the key to insert
    * @param pid[IN] the PageId to insert
    * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
    * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey);

   /**
    * Given the searchKey, find the child-node pointer to follow and
    * output it in pid.
    * Remember that the keys inside a B+tree node are sorted.
    * @param searchKey[IN] the searchKey that is being looked up.
    * @param pid[OUT] the pointer to the child node to follow.
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC locateChildPtr(int searchKey, PageId& pid);

   /**
    * Initialize the root node with (pid1, key, pid2).
    * @param pid1[IN] the first PageId to insert
    * @param key[IN] the key that should be inserted between the two PageIds
    * @param pid2[IN] the PageId to insert behind the key
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC initializeRoot(PageId pid1, int key, PageId pid2);

   /**
    * Return the number of keys stored in the node.
    * @return the number of keys in the node
    */
    int getKeyCount();
	
   /**
    * Return the number of pointers stored in the node.
    * @return the number of pointers in the node
    */
    int getPointerCount();

   /**
    * Read the content of the node from the page pid in the PageFile pf.
    * @param pid[IN] the PageId to read
    * @param pf[IN] PageFile to read from
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC read(PageId pid, const PageFile& pf);
    
   /**
    * Write the content of the node to the page pid in the PageFile pf.
    * @param pid[IN] the PageId to write to
    * @param pf[IN] PageFile to write to
    * @return 0 if successful. Return an error code if there is an error.
    */
    RC write(PageId pid, PageFile& pf);
	
	RC test();

   /**
    * Find the key and pid associated with the eid of the NonLeaf
    * @param eid[IN] the PageId to look up
    * @param key[OUT] the key of that slot
	* @param pid[OUT] the PageId of that slot
    * @return 0 if successful. Return an error code if there is an error.
    */	
	RC readEntry(int eid, int& key, PageId& pid);
	
   /**
    * Return the pid of the last pointer node.
    * @return the PageId 
    */
	PageId getLastNodePtr();
	
  private:
   /**
    * The main memory buffer for loading the content of the disk page 
    * that contains the node.
    */
    char buffer[PageFile::PAGE_SIZE];
}; 

#endif /* BTNODE_H */
